A known method for graphically modeling an object is to approximate the curvature of the object by dividing the object into a series of adjacent strips or fans and then dividing each strip or fan into a series of adjacent triangles whose vertices lay on the edge of the strip or fan. For example, FIG. 1 shows object 100 that has been divided into strips and triangles in accordance with this technique. Strips 101 and 103 are immediately adjacent to one another and define object 100. Each strip is further partitioned into a set of triangles. For example, strip 101 is divided into triangles 115, 125, 135, and so on, while strip 103 is partitioned into triangles 145, 155, 165 and so on. It is noted that the triangles are positioned within a three-dimensional space defined by the object to be rendered. Therefore, the triangles need not reside in the same plane and, indeed, are likely to be non-planar with respect to one another as they are positioned around the three-dimensional object.
Shown in FIG. 2 is a known data structure 200 for storing a strips and fans representation of an object. The triangles of the representation have been deconstructed into a vertex array 210 and an index list 220. Vertex array 210 stores information related to the vertices of the triangles. Specifically, each entry of vertex array 210 contains, among other parameters, the three-dimensional coordinates of a vertex. For example, the three-dimensional coordinates of vertices 116, 118, 120, and 122 are shown as entries in array 210. It is noted that the vertices of an object are ordinarily grouped together, but are in no particular order within the group. For example, in FIG. 2 the order of the entries corresponds to vertices 122, 118, 120, and 116. It is further noted that the coordinates stored in array 210 describe the positioning of the vertices with respect to one another in a three-dimensional space wholly defined by object 100. In other words, the coordinates define only the surface of the object, not the surrounding space.
Index list 220 stores instructions for reconnecting the vertices of the triangles within the strips of object 100. For example, the instructions relating to the reconstruction of triangle 115 are shown in index list 220. Since triangle 115 is considered, in this example, to be the first triangle in strip 101, instructions for this triangle are immediately preceded by a “start strip” instruction. The number of vertices representing a strip is encoded in the respective “start strip” instruction. This is followed by the next three instructions, which correspond to vertices 116, 118, and 120. Each instruction pair 116-118, 118-120, and 120-116, represent a connection between vertices. Thus triangle 115 is reconstructed.
Once the initial triangle in a strip is complete, a degree of efficiency is achieved by the strips and fans method. This is because each remaining triangle within the strip builds upon the preceding triangle and may be defined by reference to one additional vertex. For example, continuing with strip 101, triangle 125 shares vertices 118 and 120 with triangle 115 and may easily be defined with an additional reference to vertex 122. The technique described above capitalizes on this fact by grouping and processing the connections between vertices 118, 120, and 122 as the third through fifth instructions of index list 220. Since vertex 118 and vertex 120 have been connected in the reconstruction of triangle 115, additional connections to vertex 122 need only be made. Triangle 135 and those following in strip 101 are reconstructed in a similar fashion.
As each triangle is being reconstructed, the corresponding vertices must have certain operations performed on them in order to position them properly on the screen. Firstly, each vertex is positioned within a three-dimensional space by a geometric transformation such as a translation, a rotation, a scaling, or a combination of these functions. This transformation is performed in order to track the motions of the object to be rendered. Each vertex then may be optionally lighted before being projected from its three-dimensional space into a two-dimensional perspective. The result of this operation is to project each of the vertices in object 100 onto a flat screen that may then be rendered using a standard rendering pipeline.
Shown in FIG. 3 is a known pipeline system 300 for rendering three-dimensional objects from graphical data stored in a data structure like that shown in FIG. 2. Memory 310 is divided into an input database 311 that includes index list 220 and vertex array 210, and an output database 313 that stores transformed triangles. As described above, vertex array 210 and index list 220 store the graphical data of an object that has been modeled using the strips and fans technique. In response to a command from a user or a software application, geometry processor 320 initiates the rendering of a stored image by entering the corresponding rendering routine. Part of this routine is responsible for collecting all of the input data required to reconstruct each triangle of the object. The input data consists of index list 220, which is referenced via pointer 321, and vertex array 210, which is referenced by pointer 323. At the outset, pointer 321 corresponds to the start of instructions for rendering object 100. As described above, each instruction in the index list is either a start-strip command or an instruction to reference an entry in the vertex array. In response to receiving a start-strip command, processor 320 reads the number of vertices in the strip from the command and enters this number into a count register. It then specifies in a format register whether a strip or a fan is to be rendered, and indicates in a continuation register whether vertices from the last strip are to be carried over into the next. In response to accessing an index instruction in index list 220, processor 320 is instructed to read, via pointer 323, a corresponding vertex-array entry, entry 211 for example. As described above, vertex-array entry 211 stores the three-dimensional coordinates of a triangle vertex. In order to determine the two-dimensional screen coordinates for the vertex, the processor, in accordance with the motions of the object described by the user or the software application, reads and transforms the coordinates from vertex-array entry 211 and lights the vertex in accordance with the lighting, blocking, and shadowing parameters created by other rendered objects within the locale of the vertex in question. The result is to transform the three-dimensional model coordinates into a set of two-dimensional transformed, or screen, coordinates. Once the coordinates of a vertex have been transformed and lighted, the screen coordinates are then used by processor 320 to assemble the respective triangle, which is then stored in output database 313 of memory 310. The triangle is read by renderer 330 as needed and rendered on screen 340, thus producing the screen perspective viewed by the user.
Although the technique and system described above efficiently reconstruct subsequent triangles by building on an initial triangle, this efficiency is limited to the reconstruction of triangles within a strip. For example, with reference to FIG. 1, this can be seen in the reconstruction of triangle 145. Triangle 145 shares vertices 116 and 120 with completed triangle 115 and could easily be reconstructed by further reference to vertex 124. However, the described method builds triangle 145 by reprocessing and reconnecting vertices 116 and 120. These actions are redundant. With respect to the system of FIG. 3, this inefficiency translates into numerous redundancies for processor 320. Processor 320 must twice read, twice transform, and twice light the coordinates of model vertices 116 and 120, as well as twice connect, twice assemble and twice store the connection between these vertices. Thus, as implemented by system 300, this method produces redundancies in the processing of data, resulting in (1) decreased rendering speed due to the increased number of required computation cycles, (2) greater memory requirements due to the storage of assembled triangles which contain redundant data, and (3) inefficient use of the available memory bandwidth due to the passage of redundant data and assembled triangles between elements of the system. Thus a need exists for a method and system for processing index instructions and vertex data in a manner that reduces data redundancies and increases rendering speed.